package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *
 * @param head ListNode类
 * @param x int整型
 * @return ListNode类
 */
func partition(head *ListNode, x int) *ListNode {
	// write code here
	return solve(head, nil, nil, x)
}

func solve(head *ListNode, pre *ListNode, h *ListNode, x int) *ListNode {
	if head == nil {
		return h
	}
	if head.Val >= x {
		if pre == nil {
			return solve(head.Next, head, head, x)
		} else {
			next := head.Next
			pre.Next = head
			head.Next = nil
			return solve(next, head, h, x)
		}
	} else {
		head.Next = solve(head.Next, pre, h, x)
		return head
	}
}

func main() {
	head := ll([]int{1, 4, 3, 2, 5, 2}, &ListNode{})
	head = partition(head, 3)
	for head != nil {
		fmt.Println(head.Val)
		head = head.Next
	}
}

func ll(nums []int, head *ListNode) *ListNode {
	fnode := head
	for _, num := range nums {
		temp := ListNode{Val: num}
		head.Next = &temp
		head = &temp
	}
	return fnode.Next
}
